MOD = 10 ** 9 + 7

# 定义状态矩阵：dp[n][k][m]
MAX_N, MAX_M, MAX_K = 50, 100, 50
DP = [[[0] * (MAX_M + 1) for _ in range(MAX_K + 1)] for _ in range(MAX_N + 1)]

# 所有长度为1的数组的搜索代价都为1
for j in range(1, MAX_M + 1):
    DP[1][1][j] = 1

for i in range(2, MAX_N + 1):
    for s in range(1, min(MAX_K, i) + 1):  # 搜索代价不会超过数组长度
        prefix = 0
        for j in range(1, MAX_M + 1):
            DP[i][s][j] = (DP[i - 1][s][j] * j + prefix) % MOD
            prefix += DP[i - 1][s - 1][j]


class Solution:
    def numOfArrays(self, n: int, m: int, k: int) -> int:
        return sum(DP[n][k][j] for j in range(1, m + 1)) % MOD


if __name__ == "__main__":
    print(Solution().numOfArrays(2, 3, 1))  # 6
    print(Solution().numOfArrays(5, 2, 3))  # 0
    print(Solution().numOfArrays(9, 1, 1))  # 1
    print(Solution().numOfArrays(50, 100, 25))  # 34549172
    print(Solution().numOfArrays(37, 17, 7))  # 418930126
